The preferred embodiment concerns a method and a device for interpolation and correction of an image.
Given a digital image present as a computer-readable file, the necessity often exists to provide the image in a different resolution than as it originally exists. This in particular applies given an image scanned in by means of a scanner, which image often should be output at a different resolution than as was acquired via the optic and the sensor of the scanner.
The optical imaging via the real optic (objective) onto a scanner is additionally connected with a series of shortcomings that are caused by the optic, the sensor, the subsequent analog amplifications and the non-ideal sampling. Given superior scanners these deviations are corrected with known methods. For correction of the image it is known to use FIR filters (FIR: Finite Impulse Response), IIR filters (IIR: Infinite Impulse Response) and non-linear filters such as pruning or median filters. Non-linear filter methods are less suitable for correction of the optical/electronic acquisition system than for correction of local disruptions such as, for example, scratches in the document.
The alteration of the resolution of an image is executed by means of interpolation methods. The interpolation methods used most frequently are bilinear interpolation, bi-quadratic interpolation and two-dimensional interpolation with B-splines.
In superior scanners an acquired image is initially transformed into the desired resolution by means of an interpolation and a correction of the image is subsequently implemented. The interpolation can hereby also be executed in a plurality of steps in order to, for example, initially equalize the image and then change the resolution.
The effect of conventional interpolation methods on an image in the depiction in frequency space is subsequently explained using FIGS. 4-7. An image is represented by oscillations along a line in frequency space. FIG. 4 shows the influence of the bilinear interpolation given a shift of dx=0.25 pixels, by which is meant ¼ of the interval between two pixels. The normalized spatial frequency is plotted on the abscissa up to the Nyquist limit (at 0.5). The Nyquist frequency is the spatial frequency that represents a line of successive black and white image points. One recognizes that the greater the spatial frequency, the more significantly that the amplitude decreases (FIG. 4). This means that, given the bilinear interpolation, fine contrasts (i.e. lines lying close to one another) are weakened given a shift of dx=0.25. A shift of dx=0.25 is, for example, frequently applied given the conversion of an image from 300 DPI to 233 DPI.
The phase curve over the normalized frequency is shown in FIG. 5 for a shift of dx=0.25. For an optimal interpolation function that should implement an image shift by a ¼ pixel, the phase shift via the frequency would have to yield a straight line that goes through the origin and has a value of 45° given the Nyquist frequency. This desired function is shown dashed in FIG. 5. The phase error amounts to 4.5° at half of the Nyquist limit (i.e. 2.5% relative to the pixel length) and then rises sharply up to the Nyquist limit.
FIGS. 6 and 7 show the corresponding diagrams for an interpolation of dx=0.5 pixels. From FIG. 6 one can learn that the amplitude is more strongly damped given an interpolation of dx=0.5 pixels. To the contrary, a phase error does not occur given this interpolation (FIG. 7).
Given a bi-quadratic interpolation or given a splines interpolation, the errors are less than given a bilinear interpolation. However, it applies for all conventional interpolation methods that amplitude and phase errors arise that are dependent on the magnitude of the shift. Since the necessary shift varies across the image for arbitrary interpolations, these errors are not spatially differently developed in the interpolated image.
From U.S. Pat. No. 5,301,266 a method arises in which an image is initially filtered in frequency space and the image is subsequently transferred into classical three-dimensional space in which an interpolation is executed.
A method and a system with which a signal should be processed, which signal should exhibit an interference in the range of its high-frequency components, arises from EP 1 041 510 A2. Such interferences are in particular caused given a linear interpolation. Small 2-dimensional FIR filters are used for correction of such interferences (in particular given the processing of images), in particular inverse filters that correct a lowpass characteristic caused by the interpolation. Different filters that are calculated in advance and stored in filter banks are used for the individual interpolation steps. Each such filter corrects the interference in the frequency response that has been caused by the preceding interpolation.
These known methods for changing the resolution and correction of a digital image are not in the position to compensate these errors with high quality since the information necessary for this is no longer available after an interpolation step. Since the interpolation errors are very extensive per region, the conventional methods exhibit significant deficiencies that cannot be corrected.
A method for simultaneous interpolation and filtering of images arises from COURMONTAGEN, P.; CAVASSILAS, J. F.; “An interpolation-filtering method for noise-corrupted images” from Digital Signal Processing, 1997, Volume 2, page 1091-1094. The image is hereby transformed in frequency space by means of a Fourier transformation. Both the filtering and the interpolation can be respectively executed in frequency space via a multiplicative operation, such that both operations (the filtering and the interpolation) can be executed simultaneously. However, since this operation is located in frequency space, these operations must respectively be executed across the entire image. Given images with an image size of 256×256 image points, an operation is thus possible without further techniques with conventional computers. Give larger image formats it is not possible to execute this in a short time span even with powerful personal computers. In any case, this method in frequency space cannot be used to simultaneously interpolate and filter images in real time. The general principles of Fourier transformation on which this method is based are explained on page 108 in IWAINSKY A., WILHELMI W., Lexikon der Computergrafik und Bildverarbeitung, Vieweg Verlagsgesellschaft, 1994.